/**
 * 
 */
package dp;

/**
 * @author Michael
 *          number: 1  2  3  4
 * fibnacci number: 0, 1, 1, 2
 */
public class FibonacciNumbers {

	
	public static long fibnacciRecursive(int n) {
		assert (n > 0);
		
		if (n <= 2)
			return n - 1;
		return fibnacciRecursive(n - 1) + fibnacciRecursive(n - 2);
	}
	
	public static long fibonacciUsingMemoization(int n, long[] computed) {
		assert (n > 0);
		
		if (n <= 2) 
			return n - 1;
		if (computed[n - 1] != 0)
			return computed[n-1];

		computed[n - 1] = fibonacciUsingMemoization(n - 1, computed) +
				          fibonacciUsingMemoization(n - 2, computed);
		
		return computed[n - 1];
	}
	
	public static long fibnacciUsingDP(int n) {
		assert (n > 0);
		if (n <= 2)
			return n - 1;
		int p1 = 1, p2 = 0, f = 1;
		for (int i = 3; i <= n; ++i) {
			f = p1 + p2;
			p2 = p1;
			p1 = f;
		}
		
		return f;
	}
	
	
	/**
	 * 
	 */
	public FibonacciNumbers() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 10;
		long[] computed = new long[n];
		for (int i = 1; i <= n; ++i) {
			System.out.printf("%d ", fibonacciUsingMemoization(i, computed));
		}
		System.out.println();
		
		System.out.println(fibonacciUsingMemoization(n, new long[n + 1]) + " "
				+ fibnacciUsingDP(n));
	}
}
